'''
https://leetcode.cn/problems/maximum-running-time-of-n-computers/description/
'''

from typing import List


class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        def can_run_m_minutes(m):
            # 能否运行m分钟
            n_big_capacity_batteries, fragment_capacity = 0, 0
            for battery in batteries:
                if battery < m:
                    fragment_capacity += battery
                else:
                    n_big_capacity_batteries += 1
            # 大电池直接分走
            # 剩余的碎片电池，能否凑够容量，以使得剩余的电脑都可以运行m分钟
            return (n - n_big_capacity_batteries) * m <= fragment_capacity

        l, r = 0, sum(batteries)
        maximum_can_run_minutes = 0
        while l <= r:
            minutes = (l + r) // 2
            if can_run_m_minutes(minutes):
                maximum_can_run_minutes = minutes
                l = minutes + 1
            else:
                r = minutes - 1
        return maximum_can_run_minutes